package leetcode100;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

// TODO 递归 【-】 从前序与中序遍历序列构造二叉树
// TODO https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/solution/leetcode-105-cong-qian-xu-yu-zhong-xu-bi-3r09/

class lc100_0105 {

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return dfs(preorder, inorder);
    }

    private TreeNode dfs(int[] pre, int[] mid) {
        // 递归终止条件
        int n = pre.length;
        if (n == 0) {
            return null;
        }

        // 继续递归 + 保存结果
        TreeNode tmpNode = new TreeNode(pre[0]);
        int i = 0;
        for (; i < mid.length; i++) {
            if (mid[i] == pre[0]) {
                break;
            }
        }
        tmpNode.left = dfs(Arrays.copyOfRange(pre, 1, 1+i), Arrays.copyOfRange(mid, 0, i));
        tmpNode.right = dfs(Arrays.copyOfRange(pre, 1+i, n), Arrays.copyOfRange(mid, i+1, n));
        return tmpNode;
    }
}